#include <iostream>
using namespace std;

class ListNode{
public:
	int* data;
	ListNode* next;
};

class Test{
public:
	// 从首元结点开始，不带头结点
	ListNode* reverseList(ListNode* head) {
		ListNode* pre = NULL;
		ListNode* cur = head;
		while(cur){
			ListNode* tmp = cur->next;
			cur->next = pre;
			// 迭代
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
};

class Test2 {
public:
	ListNode* reverse(ListNode* pre,ListNode* cur){
		if(cur == NULL){
			return pre;
		}
		ListNode* tmp = cur->next;
		cur->next = pre;
		return reverse(cur,tmp);
		
	}
	ListNode* reverseList(ListNode* head) {
		return reverse(NULL,head);
	}
};

class Test3 {
public:
	ListNode* reverseList(ListNode* head) {
		if(head == NULL) return NULL;
		if(head->next == NULL) return head;
		ListNode* last = reverseList(head->next);
		head->next->next = head;
		head->next = NULL;
		return last;
	}
}; 
int main(){
	
	return 0;
}
